package LinkedList;

public class ReverseKGroup {
    public static void main(String[] args) {

    }

    public ListNode reverseKGroup(ListNode head, int k){
        if(head == null || k <= 1) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;

        while(head != null){
            // 找到一组的尾巴节点，主要是根据k的值进行遍历
            int count = 0;
            ListNode tail = pre;
            while(count < k && tail.next != null){
                tail = tail.next;
                count++;
            }

            // 先保存一下下一组的头节点
            ListNode nextGroupHead = tail.next;
            // 翻转K个一组的链表
            ListNode[] reversed = reverse(head, tail);
            head = reversed[0];
            tail = reversed[1];

            // 把前一段链表和这一段的新头连接起来，把这一段尾巴跟下一段的头连接起来
            pre.next = head;
            tail.next = nextGroupHead;

            // pre移到当前段的尾巴，head移到下一组的头准备新一轮遍历
            pre = tail;
            head = nextGroupHead;
        }
        return dummy.next;
    }

    private ListNode[] reverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next; // 反转区间后面那个节点
        ListNode cur = head;       // 从当前 head 开始反转

        while (prev != tail) {
            ListNode next = cur.next; // 暂存下一个节点
            cur.next = prev;          // 当前节点指向前一个节点（反转核心），第一次进入将prev赋值给cur.next,可以理解为1 ——> 4, 然后慢慢加入，2 -> 1 -> 4
            prev = cur;               // prev 前移
            cur = next;               // cur 前移
        }
        return new ListNode[]{tail, head}; // 返回新的 [头,尾]
    }
}
